package leetcode.editor.cn.dsa23_graph;
//节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
//
// 示例1: 
//  输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
// 输出：true
// 
// 示例2:
//  输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [
//1, 3], [2, 3], [3, 4]], start = 0, target = 4
// 输出 true
//
// 提示： 
// 节点数量n在[0, 1e5]范围内。
// 节点编号大于等于 0 小于 n。 
// 图中可能存在自环和平行边。 
// 
// Related Topics 图 
// 👍 20 👎 0

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class RouteBetweenNodesLcci0401 {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
            // graph = [[0, 1], [0, 2], [1, 2], [1, 2]]
            // 建立邻接表列表，每个邻接表都是一个 ArrayList，多个邻接表构成一个列表
            ArrayList<ArrayList<Integer>> adj = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                adj.add(new ArrayList<>());
            }
            for (int i = 0; i < graph.length; i++) {
                // 节点数据值作为邻接表列表索引
                // 0 -> [1,2]   1 -> [2,2]   2 -> []
                adj.get(graph[i][0]).add(graph[i][1]);
            }
            // 队列存储当前已经访问过尚未扩展的节点
            Queue<Integer> nodeQueue = new LinkedList<>();
            // 数组表示节点是否已被访问过
            boolean[] visited = new boolean[n];
            nodeQueue.add(start);
            visited[start] = true;
            // 注意和树的层次遍历代码略有不同，图没有层次的概念
            // 因此每出队一个顶点，直接将顶点的邻居节点全部加入队列即可
            while (!nodeQueue.isEmpty()) {
                int currentVertex = nodeQueue.poll(); // 当前顶点
                // 当前顶点的邻接点
                ArrayList<Integer> adjacency = adj.get(currentVertex);
                // 广度优先：扩展当前节点的邻居
                for (Integer vert : adjacency) {
                    if (vert == target) return true; // 找到通路
                    if (!visited[vert]) { // 如果该邻居没有被访问过
                        visited[vert] = true;
                        nodeQueue.add(vert); // 入队
                    }
                }
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}